class CreateLinkNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}

// 单向链表
class MyLinkedList {
    constructor() {
        this._head = null   //头节点
        this._tail = null    //尾节点
        this._size = null   //节点数量
    }
    // 获取指定下标节点
    getLinkNode (index) {
        if (index < 0 || index >= this._size) return null
        // 定义虚拟节点
        let curr = new CreateLinkNode(0, this._head)
        // 获取目标节点的上一个节点
        while (index--) {
            curr = curr.next
        }
        return curr.next
    }

    // 获取指定下标节点值
    getNodeValue (index) {
        const node = this.getLinkNode(index)
        return node.val
    }

    // 插入头节点
    addAtHead (val) {
        const node = new CreateLinkNode(val, this._head)
        this._head = node
        this._size++
        if (!this._tail) {
            this._tail = node
        }
    }

    // 插入尾节点
    addAtTail (val) {
        const node = new CreateLinkNode(val, null)
        this._size++
        // 判断尾节点是否存在,尾节点指向node
        if (this._tail) {
            this._tail.next = node  //当前尾节点的下一个元素指向node
            this._tail = node   //修改尾节点为node
            return
        }
        // 不存在尾节点,则指定头节点和尾节点
        this._head = node
        this._tail = node

    }

    // 插入指定下标节点之前
    addAtIndex (index, val) {
        // 如果 index 比长度更大，该节点将 不会插入到链表中
        if (index > this._size) return
        // index <= 0 ,则表示插入头节点
        if (index <= 0) this.addAtHead(val)
        // 如果 index == this._size，则表示插入尾节点
        if (index == this._size) this.addAtTail(val)
        // 获取需要插入目标节点的上一个节点
        const node = this.getLinkNode(index - 1)
        // 目标节点的上一个节点指向新创建的节点
        node.next = new CreateLinkNode(val, node)
    }

    // 删除指定下标节点
    deleteAtIndex (index) {
        // 判断下标是否有效,无效则不操作
        if (index < 0 || index >= this._size) return
        // 判断是否只存在一个节点
        if (this._size === 1) {
            this._head = null
            this._tail = null
            this._size = 0
            return
        }
        // 判断删除的是否为头节点
        if (index == 0) {
            this._head = this._head.next
            this._size--
            return
        }
        // 获取要删除的目标节点的上一个节点
        const node = this.getLinkNode(index - 1)
        // 判断是否为尾节点
        if (this._size - 1 == index) {
            node.next = null
            this._tail = node
        } else {
            node.next = node.next.next
        }
        this._size--
    }

    // 节点排序 - 升序
    orderAsc (head) {  //[1,2,3,4,5]
        const merge = function (l1, l2) {
            const dummy = new CreateLinkNode(0);
            let cur = dummy
            while (l1 && l2) {
                if (l1.val > l2.val) {
                    cur.next = l2;
                    l2 = l2.next
                } else {
                    cur.next = l1
                    l1 = l1.next
                }
                cur = cur.next
            }
            if (l1) cur.next = l1;
            if (l2) cur.next = l2;
            return dummy.next
        }

        //[5,4,3,2,1]
        const sortList = function (list) {
            if (!list || !list.next) return list
            let fast = list,
                slow = list,
                preSlow = null  //用来将链表截成两段链表
            while (fast && fast.next) {
                preSlow = slow
                slow = slow.next
                fast = fast.next.next
            }
            preSlow.next = null
            // ==>1. left --> [5,4] , right-->[3,2,1]
            // ==>2. left --> [5],   right-->4  ,merge([5,4]) --->left =[4,5]
            // ==>3. right --> left-->[3] , right -->[2,1]
            // ==>4. left -->[2],right [1], merge([2,1])-->right =[1,2] ,再merge([3],[2,1])
            // ==>5. left --->[4,5] ,right-->[1,2,3] ,再合并merge([4,5] ,[1,2,3])
            // ==>6. 返回[1,2,3,4,5]
            const left = sortList(list);
            const right = sortList(slow);
            return merge(left, right);
        }

        return sortList(head)
    }

    // 节点反转
    reverse () {
        if (this._size <= 1) return
        this._tail = new CreateLinkNode(this._head.val, null)
        let cur = this._head, pre = null
        while (cur) {
            let temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        }
        this._head = pre
    }

    // // K 个一组翻转链表,未改变头节点和尾节点
    reverseAtK (head, k) {
        if (!head || !head.next || k <= 1) return head
        const reverse = function (cur, pre) {
            while (k--) {
                let temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
            }
            return pre
        }

        let n = 1, list = cur = head

        while (cur) {
            n++
            cur = cur.next
            if (n == k) {
                return reverse(list, this.reverseAtK(cur.next, k))
            }
        }
        this._tail = cur
        return list
    }

    // 两两交换节点,未改变头节点和尾节点
    swapPairs (head) {
        debugger
        if (!head || !head.next) return head
        const swap = function (cur, pre) {
            let temp = cur.next
            cur.next = pre
            temp.next = cur
            return temp
        }
        let n = 0, list = head, cur = head
        while (cur) {
            n++
            if (n == 2) {
                return swap(list, this.swapPairs(cur.next))
            }
            cur = cur.next
        }
    }

    //重排列表
    //L0 → L1 → … → Ln - 1 → Ln   //[1,2,3,4,5]
    //L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 →...  //[1,5,2,4,3]
    reorderList (head) {
        if (!head || !head.next) return head

        const findMiddleNode = function (head) {
            let slow = head, fast = head
            while (fast && fast.next) {
                fast = fast.next.next
                slow = slow.next
            }
            return slow
        }

        const reverse = function (head) {
            let pre = null, cur = head
            while (cur) {
                let temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
            }
            return pre
        }

        const middleNode = findMiddleNode(head)
        let head2 = reverse(middleNode)

        let cur = head
        while (head2 && head2.next) {
            debugger
            let temp = cur.next
            let temp1 = head2.next

            head2.next = temp
            cur.next = head2

            cur = temp
            head2 = temp1
        }

        return head

        // debugger
        // if (!head || !head.next) return head
        // let size = 0, cur = head
        // while (cur) {
        //     size++
        //     cur = cur.next
        // }
        // const df = function (list, index, size) {
        //     debugger
        //     if (index >= size) return null
        //     let cur = list, pre = list, c = size - index
        //     while (c-- > 1) {
        //         cur = cur.next
        //     }
        //     cur.next = df(list.next, index + 2, size)
        //     if (cur.next) {
        //         pre.next = cur
        //     }
        //     return pre
        // }

        // return df(head, 0, size)
    }

    //82.删除排序链表中的重复元素II  [1,2,3,3,4,4,5] --->[1,2,5]
    deleteDuplicates (head) {
        // 删除重复节点  [1,2,2,3,4] --->[1,2,3,4]
        // let cur = head
        // while (cur) {
        //     debugger
        //     if (cur.next && cur.val == cur.next.val) cur.next = cur.next.next
        //     else cur = cur.next
        // }
        // return head

        let dummy = new CreateLinkNode(), //虚拟节点
            node = dummy,  //新建虚拟节点则不用处理头节点特殊情况
            cur = head,  //节点遍历
            flag = false  //标识节点是否为重复的节点,如果是重复的节点,则不添加到node节点中
        while (cur) {
            if (cur.next && cur.val === cur.next.val) {
                flag = true
                cur.next = cur.next.next
            } else {
                // flag 为true 表示当前节点是重复的节点
                if (!flag) {
                    node.next = cur
                    node = node.next
                }
                cur = cur.next
                flag = false
            }
        }

        node.next = null

        return dummy.next
    }

    //92.反转链表 II  按指定节点反转链表
    // head = [1,2,3,4,5], left = 2, right = 4
    // --->  [1,4,3,2,5]
    reverseBetween (head, left = 2, right = 4) {
        if (!head || !head.next || right == left) return head

        const reverse = function (head, tail) {
            let cur = head, pre = tail.next
            while (cur) {
                let temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
                if (cur == tail) {
                    tail.next = pre
                    return tail
                }
            }
        }

        let slow = head, fast = head,
            dummy = new CreateLinkNode(),
            pre = dummy;
        while (--right) {
            left--
            if (left >= 1) pre.next = fast, pre = pre.next;
            if (left > 0) slow = slow.next
            fast = fast.next
        }
        pre.next = reverse(slow, fast)
        return dummy.next
    }

    // 奇偶下标链表
    oddEvenList (head) {
        if (!head || !head.next) return head
        let cur = head.next,
            odd = head,//奇数链表的最后一位
            even = cur  //偶数链表的第一位
        while (cur && cur.next) {
            let temp = cur.next
            cur.next = cur.next.next  //将当前偶数下标的下一个节点指向下下个节点
            temp.next = even  // 奇数节点始终指向偶数节点的链表
            odd.next = temp
            odd = temp
            cur = cur.next
        }
        return head
    }

    //分隔链表
    splitListToParts (head, k) {
        let cur = head, len = 0, res = new Array(k).fill(null)
        while (cur) {
            len++
            cur = cur.next
        }

        cur = head;

        let avg = len > k ? Math.floor(len / k) : 1,
            mod = len > k ? len % k : 0,
            pre = head,
            n = 0,
            i = 0;

        while (cur) {
            let temp = cur.next
            n++
            if (n == (avg + (mod > 0 ? 1 : 0))) {
                cur.next = null
                res[i] = pre
                pre = temp
                i++
                mod--
                n = 0
            }
            cur = temp
        }

        return res
    }

    // 交换节点
    swapNodes (head, k) {
        // 交换值即可
        if (!head || !head.next) return head
        let fast = head, n = 0
        while (fast) {
            n++
            fast = fast.next
        }
        let last = n - k + 1

        if (last == k) return head

        let start = Math.min(last, k), slow = head;
        last = Math.max(last, k)
        fast = head
        n = 0

        while (fast && fast.next) {
            n++
            if (n < start) {
                slow = slow.next
            }
            if (n < last) {
                fast = fast.next
            }
            if (n == last) break;

        }

        [slow.val, fast.val] = [fast.val, slow.val]
        return head

    }

    // 从链表中删去总和值为零的连续节点
    removeZeroSumSublists (head) {
        debugger
        if (!head) return head
        let dummy = new CreateLinkNode()
        const dfs = function (link, pre) {
            debugger
            if (!link) return
            let cur = link, sum = 0, flag = false
            while (cur) {
                sum += cur.val
                if (sum == 0) {
                    pre.next = cur.next
                    flag = true
                    break;
                }
                cur = cur.next
            }
            if (!flag && !pre.next) {
                pre.next = link
            }
            dfs(flag ? cur.next : link.next, flag ? pre : pre.next)
        }
        dfs(head, dummy)
    }
    //翻倍以链表形式表示的数字
    doubleIt (head) {
        if (!head || !head.next) return head

        const reverse = function (link) {
            let pre = null, cur = link
            while (cur) {
                let temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
            }
            return pre
        }

        head = reverse(head)
        let carry = 0, cur = head, pre = null

        debugger

        while (cur) {
            debugger
            let temp = cur.next
            let v = cur.val * 2 + carry,
                mod = v % 10

            carry = Math.floor(v / 10)

            cur.val = mod

            cur.next = pre

            pre = cur

            cur = temp
        }

        if (carry) return new CreateLinkNode(carry, pre)
        else return pre
    }
}

let myLinkedList = new MyLinkedList()
//[1, 3, 2, -3, -2, 5, 5, -5, 1]
const head = [1, 8, 9], len = head.length

for (let i = 0; i < len; i++) {
    myLinkedList.addAtTail(head[i])
}

console.log(myLinkedList)
debugger
myLinkedList.doubleIt(myLinkedList._head)
